#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
using namespace std;

//int main()
//{
//	int n;
//	cin >> n;
//	int arr[4] = { 0 };
//	if (n == 0)
//	{
//		cout << endl;
//		return 0;
//	}
//	else
//	{
//		arr[0] = 1;
//	}
//
//	for (int i = 1; i < n; i++)
//	{
//		arr[0] += arr[3];
//		arr[3] = arr[2];
//		arr[2] = arr[1];
//		arr[1] = arr[0];
//	}
//	int sum = 0;
//	for (int i = 0; i < 4; i++)
//	{
//		sum += arr[i];
//	}
//	 
//	cout << sum << endl;
//	return 0;
//}

//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        int dest = 0;
//        int cur = 0;
//        while (cur < nums.size())
//        {
//            if (nums[cur] != 0)
//            {
//                nums[dest++] = nums[cur];
//            }
//            cur++;
//        }
//        while (dest < nums.size())
//        {
//            nums[dest++] = 0;
//        }
//    }
//};

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int i = 0;
        int cur = -1;
        int n = arr.size();
        while (cur < n)
        {
            if (arr[i] != 0)
            {
                cur++;
            }
            else
            {
                cur += 2;
            }
            if (cur >= n - 1)
                break;

            i++;

        }

        if (cur == n)
        {
            arr[cur - 1] = 0;
            i--;
            cur -= 2;
        }
        while (i >= 0)
        {
            if (arr[i] != 0)
            {
                arr[cur--] = arr[i];
            }
            else
            {

                arr[cur--] = 0;
                arr[cur--] = 0;
            }
            i--;
        }
    }
};

int main()
{

    vector<int> v({ 1,0,2,3,0,4,5,0 });
    Solution().duplicateZeros(v);
    return 0;
}